The Optimized Link State Routing Protocol (OLSR) has been developed for mobile ad hoc networks. It operates as a table driven and proactive protocol, and thus exchanges topology information with other nodes of the network regularly. The nodes which are selected as a multipoint relay (MPR) by some neighbor nodes announce this fact periodically in their topology control (TC) messages. Thereby, a node announces to the network, that it has reachability to the nodes which have selected it as an MPR. In route calculation, the MPRs are used to form the route from a given node to any destination in the network. The protocol uses the MPRs to facilitate efficient flooding of TC messages in the network.
More specifically, OLSR operates by maintaining an internal data structure within each node of local 1-hop and 2-hop neighbors, overall network connectivity, and a routing table. OLSR generates and maintains these internal data structures by exchanging three kinds of OLSR over the air (OTA) messages including HELLO messages, TC messages, MID (multiple interface declaration) messages and HNA (host and network association) messages.
The internal data structures are used in the network to populate a relay cache with next-hop node IDs indexed by final-destination node ID. A table pairing network MAC addresses and IP addresses is also maintained. HELLO messages are exchanged exclusively between 1-hop neighbors. For example, each node may generate HELLO messages every 2 seconds. They serve to establish and maintain the 1- and 2-hop neighborhood connectivity state parts of a node's internal OLSR data structures. Exchange of 1-hop neighborhood information between 1-hop neighbors serves to inform each node of its 2-hop neighborhood. This, in turn, allows each node to select MPR nodes that are used for efficient message-flooding (i.e., network broadcast). For each node, the MPRs implement a spanning tree covering the network.
Also, each node may generate TC messages that flood the network via its MPR spanning tree, typically every 5 seconds. TC messages distribute each node's relevant 1-hop neighborhood information in the form of its MPR selectors (1-hop neighbors who selected it as their MPR) to all other nodes in the network. This information is then used by each node to build its routing table. The OLSR routing table is used to fill each node's relay cache. Each node generates HNA messages that flood the network via its MPR spanning tree, e.g. every 5 seconds. HNA messages distribute each node's network mask and MAC address. HNA message information is used to fill each node's MAC address to IP address table.
Conventional OLSR may drop routes during network topology transitions. The causes may include TC messaging forwarding factors such as each node trying to minimize MPRs selected, TC messages distributed via MPR spanning trees, TC/HNA message forwarding ordering, each node's OLSR timers being de-correlated, TC message distribution race conditions and/or reverse MPR spanning tree routing. When TC messages fail to arrive for the aforementioned reasons, network topology segments can timeout and be dropped.
As mentioned above, MPR spanning trees are used by OLSR to efficiently flood a node's messages through the entire network. When a node generates a message to be flooded, it broadcasts the message to its 1-hop neighbors. Each 1-hop neighbor selected by the node as an MPR, in turn, retransmits the message. Because of how MPRs are selected, this 1-hop-MPR-neighbor forwarding gives coverage of all 2-hop neighbors. Each node receiving the message checks to see if the message has already been received, i.e., if it was a duplicate. If a duplicate was received, then the message is discarded. If a non-duplicate was received and the transmitting node had selected the receiving node as one of its MPRs, then the receiving node retransmits (i.e., forwards) the message. The retransmissions continue until no more retransmissions (forwardings) occur. Loops are avoided by discarding duplicates. The flooding process terminates when the flooded message has been delivered to all end nodes (or leaves) of the originating node's MPR spanning tree.
OLSR includes routing via reverse MPR-spanning-trees. Conventional OLSR constrains computed routes to lie along reverse paths in the destination's MPR spanning tree. Each node's MPR spanning tree should cover the entire network, i.e. that is what makes it a spanning tree. Thus any node in the network can route to a destination node by plotting a route from itself to the destination backward through branches in the destination node's MPR spanning tree, by reversing the path used by the destination node's flooded messages to reach the source node.
OLSR's reverse-MPR-spanning-tree routing works well when the network is stable, i.e. when the OLSR topology-distribution mechanism has converged so that each node in the network has the same network-level view of network topology. But during a period in which a node's local connectivity changes and MPR selection changes are being distributed across the network, problems can arise.